home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 98 / Skunkware 98.iso / src / interp / perl5.005.tar.gz / perl5.005.tar / perl5.005 / x2p / hash.c < prev    next >
C/C++ Source or Header  |  1998-02-07  |  5KB  |  233 lines
  1. /* $RCSfile: hash.c,v $$Revision: 4.1 $$Date: 92/08/07 18:29:20 $
  2.  *
  3.  *    Copyright (c) 1991-1997, Larry Wall
  4.  *
  5.  *    You may distribute under the terms of either the GNU General Public
  6.  *    License or the Artistic License, as specified in the README file.
  7.  *
  8.  * $Log:    hash.c,v $
  9.  */
  10.  
  11. #include <stdio.h>
  12. #include "EXTERN.h"
  13. #include "a2p.h"
  14. #include "util.h"
  15.  
  16. STR *
  17. hfetch(register HASH *tb, char *key)
  18. {
  19.     register char *s;
  20.     register int i;
  21.     register int hash;
  22.     register HENT *entry;
  23.  
  24.     if (!tb)
  25.     return Nullstr;
  26.     for (s=key,        i=0,    hash = 0;
  27.       /* while */ *s;
  28.      s++,        i++,    hash *= 5) {
  29.     hash += *s * coeff[i];
  30.     }
  31.     entry = tb->tbl_array[hash & tb->tbl_max];
  32.     for (; entry; entry = entry->hent_next) {
  33.     if (entry->hent_hash != hash)        /* strings can't be equal */
  34.         continue;
  35.     if (strNE(entry->hent_key,key))    /* is this it? */
  36.         continue;
  37.     return entry->hent_val;
  38.     }
  39.     return Nullstr;
  40. }
  41.  
  42. bool
  43. hstore(register HASH *tb, char *key, STR *val)
  44. {
  45.     register char *s;
  46.     register int i;
  47.     register int hash;
  48.     register HENT *entry;
  49.     register HENT **oentry;
  50.  
  51.     if (!tb)
  52.     return FALSE;
  53.     for (s=key,        i=0,    hash = 0;
  54.       /* while */ *s;
  55.      s++,        i++,    hash *= 5) {
  56.     hash += *s * coeff[i];
  57.     }
  58.  
  59.     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  60.     i = 1;
  61.  
  62.     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
  63.     if (entry->hent_hash != hash)        /* strings can't be equal */
  64.         continue;
  65.     if (strNE(entry->hent_key,key))    /* is this it? */
  66.         continue;
  67.     /*NOSTRICT*/
  68.     safefree(entry->hent_val);
  69.     entry->hent_val = val;
  70.     return TRUE;
  71.     }
  72.     /*NOSTRICT*/
  73.     entry = (HENT*) safemalloc(sizeof(HENT));
  74.  
  75.     entry->hent_key = savestr(key);
  76.     entry->hent_val = val;
  77.     entry->hent_hash = hash;
  78.     entry->hent_next = *oentry;
  79.     *oentry = entry;
  80.  
  81.     if (i) {                /* initial entry? */
  82.     tb->tbl_fill++;
  83.     if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
  84.         hsplit(tb);
  85.     }
  86.  
  87.     return FALSE;
  88. }
  89.  
  90. #ifdef NOTUSED
  91. bool
  92. hdelete(tb,key)
  93. register HASH *tb;
  94. char *key;
  95. {
  96.     register char *s;
  97.     register int i;
  98.     register int hash;
  99.     register HENT *entry;
  100.     register HENT **oentry;
  101.  
  102.     if (!tb)
  103.     return FALSE;
  104.     for (s=key,        i=0,    hash = 0;
  105.       /* while */ *s;
  106.      s++,        i++,    hash *= 5) {
  107.     hash += *s * coeff[i];
  108.     }
  109.  
  110.     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
  111.     entry = *oentry;
  112.     i = 1;
  113.     for (; entry; i=0, oentry = &entry->hent_next, entry = entry->hent_next) {
  114.     if (entry->hent_hash != hash)        /* strings can't be equal */
  115.         continue;
  116.     if (strNE(entry->hent_key,key))    /* is this it? */
  117.         continue;
  118.     safefree((char*)entry->hent_val);
  119.     safefree(entry->hent_key);
  120.     *oentry = entry->hent_next;
  121.     safefree((char*)entry);
  122.     if (i)
  123.         tb->tbl_fill--;
  124.     return TRUE;
  125.     }
  126.     return FALSE;
  127. }
  128. #endif
  129.  
  130. void
  131. hsplit(HASH *tb)
  132. {
  133.     int oldsize = tb->tbl_max + 1;
  134.     register int newsize = oldsize * 2;
  135.     register int i;
  136.     register HENT **a;
  137.     register HENT **b;
  138.     register HENT *entry;
  139.     register HENT **oentry;
  140.  
  141.     a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
  142.     bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */
  143.     tb->tbl_max = --newsize;
  144.     tb->tbl_array = a;
  145.  
  146.     for (i=0; i<oldsize; i++,a++) {
  147.     if (!*a)                /* non-existent */
  148.         continue;
  149.     b = a+oldsize;
  150.     for (oentry = a, entry = *a; entry; entry = *oentry) {
  151.         if ((entry->hent_hash & newsize) != i) {
  152.         *oentry = entry->hent_next;
  153.         entry->hent_next = *b;
  154.         if (!*b)
  155.             tb->tbl_fill++;
  156.         *b = entry;
  157.         continue;
  158.         }
  159.         else
  160.         oentry = &entry->hent_next;
  161.     }
  162.     if (!*a)                /* everything moved */
  163.         tb->tbl_fill--;
  164.     }
  165. }
  166.  
  167. HASH *
  168. hnew(void)
  169. {
  170.     register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
  171.  
  172.     tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
  173.     tb->tbl_fill = 0;
  174.     tb->tbl_max = 7;
  175.     hiterinit(tb);    /* so each() will start off right */
  176.     bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
  177.     return tb;
  178. }
  179.  
  180. #ifdef NOTUSED
  181. hshow(tb)
  182. register HASH *tb;
  183. {
  184.     fprintf(stderr,"%5d %4d (%2d%%)\n",
  185.     tb->tbl_max+1,
  186.     tb->tbl_fill,
  187.     tb->tbl_fill * 100 / (tb->tbl_max+1));
  188. }
  189. #endif
  190.  
  191. int
  192. hiterinit(register HASH *tb)
  193. {
  194.     tb->tbl_riter = -1;
  195.     tb->tbl_eiter = Null(HENT*);
  196.     return tb->tbl_fill;
  197. }
  198.  
  199. HENT *
  200. hiternext(register HASH *tb)
  201. {
  202.     register HENT *entry;
  203.  
  204.     entry = tb->tbl_eiter;
  205.     do {
  206.     if (entry)
  207.         entry = entry->hent_next;
  208.     if (!entry) {
  209.         tb->tbl_riter++;
  210.         if (tb->tbl_riter > tb->tbl_max) {
  211.         tb->tbl_riter = -1;
  212.         break;
  213.         }
  214.         entry = tb->tbl_array[tb->tbl_riter];
  215.     }
  216.     } while (!entry);
  217.  
  218.     tb->tbl_eiter = entry;
  219.     return entry;
  220. }
  221.  
  222. char *
  223. hiterkey(register HENT *entry)
  224. {
  225.     return entry->hent_key;
  226. }
  227.  
  228. STR *
  229. hiterval(register HENT *entry)
  230. {
  231.     return entry->hent_val;
  232. }
  233.